// @algorithm @lc id=100329 lang=cpp
// @title zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int search(vector<int> &nums, int target) {
        int ans = 0;
        int n = nums.size();
        if (n != 0) {
            int first = getFirstTarget(nums, target, n, 0, n - 1);
            int last = getLastTarget(nums, target, n, 0, n - 1);
            if (first > -1 && last > -1) {
                ans = last - first + 1;
            }
        }
        return ans;
    }
    // 找到第一个target
    int getFirstTarget(vector<int> &nums, int target, int length, int l, int r) {
        if (l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        int midVal = nums[mid];
        if (midVal == target) {
            if ((mid > 0 && nums[mid - 1] != target) || mid == 0) {
                return mid;
            }
            else {
                r = mid - 1;
            }
        }
        else if (midVal > target) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
        return getFirstTarget(nums, target, length, l, r);
    }
    // 找到最后一个target
    int getLastTarget(vector<int> &nums, int target, int length, int l, int r) {
        if (l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        int midVal = nums[mid];
        if (midVal == target) {
            if ((mid < length - 1 && nums[mid + 1] != target) || mid == length - 1) {
                return mid;
            }
            else {
                l = mid + 1;
            }
        }
        else if (midVal > target) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
        return getLastTarget(nums, target, length, l, r);
    }
};